package com.linyaonan.leetcode.medium._473;

import java.util.Arrays;

/**
 * 你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
 *
 * 如果你能使这个正方形，则返回 true ，否则返回 false 。
 *
 * 输入: matchsticks = [1,1,2,2,2]
 * 输出: true
 * 解释: 能拼成一个边长为2的正方形，每边两根火柴。
 *
 * 提示:
 *
 * 1 <= matchsticks.length <= 15
 * 1 <= matchsticks[i] <= 10^8
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/matchsticks-to-square
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    public long t;

    /**
     * 思路一：首先将原数组拆分为和相等的子数组
     * 然后使用遍历拆成4个数组
     * @param matchsticks
     * @return
     */
    public boolean makesquare(int[] matchsticks) {
        // 异常边界
        if (matchsticks == null || matchsticks.length <= 3) {
            return false;
        }

        // 统计出最大值以及总和
        long all = 0L;
        int max = matchsticks[0];

        for (int n : matchsticks) {
            all += n;
            max = Math.max(max, n);
        }

        // 存在最大值大于4分之一的总和
        if (max > (all << 2)) {
            return false;
        }

        // 总和并不为4的整数倍
        if (all % 4 != 0) {
            return false;
        }

        t = all >> 2;

        // 用来表示该位的数值是否已被使用
        boolean[] isUse = new boolean[matchsticks.length];
        return bt(4, 0, 0, isUse, matchsticks);
    }

    public boolean bt(int group, int count, int start, boolean[] isUse, int[] matchsticks) {
        // 表示找到一组
        if (group == 0) {
            return true;
        }
        // 表示找到一条边
        if (count == t) {
            return bt(group-1, 0, 0, isUse, matchsticks);
        } else {
            for (int i = start; i < isUse.length; i++) {
                if (!isUse[i] && count + matchsticks[i] <= t) {
                    isUse[i] = true;
                    if (bt(group, count + matchsticks[i], i, isUse, matchsticks)) {
                        return true;
                    }
                    isUse[i] = false;
                }
            }
        }

        return false;
    }


}